package demo1;

import java.util.Stack;

class Solution {
/*
    public int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        //递归的出口  不满足这个条件 那么就是没有了左树 或者右树
        if(inbegin > inend) {
            return null;
        }
        //先创建根节点
        TreeNode root = new TreeNode(preorder[preIndex]);//根节点

        //找到根节点 所在中序遍历中的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        // 先创建左树 再创建右树   本身是在遍历： 前序遍历
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }*/
/*

    public int postIndex = 0;


    public TreeNode buildTree(int[] inorder, int[] postorder) {

        postIndex = postorder.length-1;

        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }


    private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
        //递归的出口  不满足这个条件 那么就是没有了左树 或者右树
        if(inbegin > inend) {
            return null;
        }
        //先创建根节点
        TreeNode root = new TreeNode(postorder[postIndex]);//根节点

        //找到根节点 所在中序遍历中的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;
        // 先创建右树    再创建左树   本身是在遍历： 后序遍历

        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);

        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }*/


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        if(p == root || q == root) {
            return root;
        }

        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);

        if(leftRet != null && rightRet != null) {
            return root;
        }else if(leftRet != null) {
            return leftRet;
        }else {
            return rightRet;
        }
    }



}